﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.ListNode.CircularLinkedList
{
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int val = 0, ListNode next = null)
        {
            this.val = val;
            this.next = next;
        }
    }
    //========================================== 环形链表
    //给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null
    //为了表示给定链表中的环，使用整数pos来表示链表尾链接到链表中的位置（索引从0开始）。如果pos为-1，则该链表中没有环
    //不允许修改给定的链表
    //=====判断链表是否有环
    //使用快慢指针法，分别定义fast和slow指针，从头节点触发，falst指针每次移动两个节点，slow每次移动一个节点，如果falst和slow在途中相遇，说明这个链表有环
    //=====寻找环的入口
    //设从头节点到环形入口节点的节点数为x，环形入口节点到fast指针和slow指针相遇节点的节点数为y，从相遇节点再到环形入口节点的节点数为z,
    //那么相遇时：slow指针走过的节点数为(x+y),fast指针走过的节点数为（x+y+n(x+y)),n为fast指针在环内走了n圈才遇到slow指针，(y+z)即为一圈内节点的个数A
    //fast指针一次走两个节点，slow指针一次走一个节点，所以fast指针走过的节点数=slow指针走过的节点数*2
    //即有：(x+y) * 2 = x+y+n(y+z)===消去(x+y)==>x+y = n(y+z)======>x = n(y+z) -y =====>x=(n-1)(y+z)+z此处n一定大于等于1，因为fast指针至少要多走一圈才能跟slow相遇
    //有公式：x=(n-1)(y+z)+z  
    //当n=1,x = z。意味着从头节点出发一个指针A，从相遇节点出发一个指针B，两个指针每次只走一个节点，则他们相遇时就是环形入口
    //当n>1。 当A,B两个指针同时出发时,B指针在环内走了n-1圈才和A指针在环形入口相遇
    //======为什么相遇时慢指针还未在环中走满一圈，即slow走过的节点是是(x+y)，而不是x+n(y+z)+y
    //fast指针的速度是slow指针的速度的两倍，假设他们同时入环，则他们相遇时应在入口处，此时fast指针走了两圈，slow指针刚走满一圈
    //已知fast指针必然比slow指针先入环，则他们相遇时，必然slow指针还未走满一圈。

    //=== 从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
    class CircularLinkedList
    {
        public ListNode DetectCycle(ListNode head)
        {
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null)
            {
                slow = slow.next;
                fast = fast.next.next;
                //快慢指针相遇，此时从head和相遇点，同事查找直至相遇
                if(slow == fast)
                {
                    ListNode index1 = fast;
                    ListNode index2 = head;
                    while(index1 != index2)
                    {
                        index2 = index2.next;
                        index1 = index1.next;
                    }
                    return index2;//返回环入口
                }
            }
            return null;
        }
    }
}
